package com.cat.monotonicStack;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximal-rectangle/
 * @create 2025/8/13 15:14
 * @since JDK17
 */

public class Solution04 {
    static int N = 301, top;
    static int[] stack = new int[N];

    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length, ans = 0, m = matrix[0].length, cnt = 0;
        int[] prefix = new int[m];
        top = 0;
        for (int i = 0; i < m; i++) {
            if (matrix[0][i] == '1') {
                prefix[i] = 1;
            }
        }
        for (int i = 0; i < m; i++) {
            int start = i;
            while (i < m && prefix[i] != 0) i++;
            ans = Math.max(ans, i - start);
        }
        int l, r, cur;
        for (int i = 1; i < n; i++) {
            top = 0;
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    prefix[j]++;
                } else {
                    prefix[j] = 0;
                }
                while (top > 0 && prefix[stack[top - 1]] > prefix[j]) {
                    cur = --top;
                    l = cur == 0 ? -1 : stack[cur - 1]; // 左闭右闭
                    r = j;
                    ans = Math.max(ans, prefix[stack[cur]] * (r - l - 1));
                }
                stack[top++] = j;
            }
            while (top > 0) {
                cur = --top;
                l = cur == 0 ? -1 : stack[cur - 1];
                r = m;
                ans = Math.max(ans, prefix[stack[cur]] * (r - l - 1));
            }
        }
        return ans;
    }
}
